// ---------------------------- 普通队列 ------------------------------------

// 队列是遵循 FIFO（First In First Out，先进先出）原则的一组有序的项。
// 队列在尾部添加新元素，并从顶部移除元素。
// 最新添加的元素必须排在队列的末尾。
// 队列只有 入队 push() 和出队 pop()。

// enqueue(element)：向队列尾部添加新项。
// dequeue()：移除队列的第一项，并返回被移除的元素。
// front()：返回队列中第一个元素，队列不做任何变动。
// isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
// size()：返回队列包含的元素个数，与数组的 length 属性类似。
// print()：打印队列中的元素。
// clear()：清空整个队列。

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }

  print() {
    console.log(this.items.toString());
  }
}


// ---------------------------- 优先队列 ------------------------------------

// 优先队列中元素的添加和移除是依赖优先级的。

// 实现一个优先队列，有两种选项：

// 1. 设置优先级，根据优先级正确添加元素，然后和普通队列一样正常移除
// 2. 设置优先级，和普通队列一样正常按顺序添加，然后根据优先级移除

// enqueeue(element)：向队列尾部添加新项。
// dequeue()：移除队列的第一项，并返回被移除的元素。
// front()：返回队列中第一个元素，队列不做任何变动。
// isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
// size()：返回队列包含的元素个数，与数组的 length 属性类似。
// print()：打印队列中的元素。
// clear()：清空整个队列。

// 按照第一种做法 最小优先级队列 最大队列 把判断的地方 < 换为 > 即可

class MinPriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueeue(item, priority) {
    const queueItem = {
      item,
      priority
    }
    if (this.isEmpty()) {
      this.items.push(queueItem);
    } else {
      let isAdd = false;
      for (let index = 0; index < this.size(); index++) {
        if (queueItem.priority < this.items[index].priority) {
          this.items.splice(index, 0, queueItem);
          isAdd = true
          break;
        }
      }
      if (!isAdd) {
        this.items.push(queueItem);
      }
    }
  }

  dequeue() {
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  print() {
    console.log(JSON.stringify(this.items));
  }
}

// const minQueue = new MinPriorityQueue();

// minQueue.enqueeue('jack', 2);
// minQueue.enqueeue('wade', 4);
// minQueue.enqueeue('iversion', 3);
// minQueue.enqueeue('kobe', 1);

// minQueue.print();


// ---------------------------- 循环队列 ------------------------------------

// 定义
// 循环队列，顾名思义，它长得像一个环。把它想像成一个圆的钟就对了。

// 关键是：确定好队空和队满的判定条件。

// 循环队列的一个例子就是击鼓传花游戏（Hot Potato）。
// 在这个游戏中，孩子们围城一个圆圈，击鼓的时候把花尽快的传递给旁边的人。
// 某一时刻击鼓停止，这时花在谁的手里，谁就退出圆圈直到游戏结束。
// 重复这个过程，直到只剩一个孩子（胜者）。

const HotPotato = (m, n) => {
  // 创建队列
  const queue = new Queue();
  // 把数据加入队列
  if(m > 0) {
    for (let index = 1; index <= m; index++) {
      queue.enqueue(index);
    }
  }

  let item = '';
  while(queue.size() > 1) {
    // 没到 n 之前, 把第一个移到最后一个
    for (let i = 1; i < n; i++) {
      const item = queue.dequeue();
      queue.enqueue(item);
    }
    // 循环结束后,移除第 n 个
    item = queue.dequeue();
    console.log(`${item}被淘汰`);
  }
  // 这时队列中只有一个 就是胜利者
  const winner = queue.dequeue();
  console.log(`${winner}胜利!`);
  return winner;
}

// HotPotato(10, 3);